from functools import cache
from typing import *

from collections import deque
from math import inf


class Solution:

    def minNumberOfSemesters(self, n: int, relations: List[List[int]],
                             k: int) -> int:
        ins = [0] * n
        nexts = [[] for _ in range(n)]
        for x, y in relations:
            ins[y - 1] += 1
            nexts[x - 1].append(y - 1)

        @cache
        def f(rest, mask):
            if rest == 0:
                return 0
            ans = inf
            enum: int = mask
            while enum > 0:
                if enum.bit_count() <= k:
                    done = 0
                    for i in range(n):
                        if (enum >> i) & 1 == 1:
                            for j in nexts[i]:
                                ins[j] -= 1
                                if ins[j] == 0:
                                    done |= 1 << j
                    ans = min(ans, f(rest ^ enum, (mask ^ enum | done)))
                    for i in range(n):
                        if (enum >> i) & 1 == 1:
                            for j in nexts[i]:
                                ins[j] += 1
                enum = (enum - 1) & mask
            return ans + 1

        mask = 0
        for i in range(n):
            if ins[i] == 0:
                mask |= 1 << i
        return f((1 << n) - 1, mask)


class Solution:

    def minNumberOfSemesters(self, n: int, relations: List[List[int]],
                             k: int) -> int:
        f = [inf] * (1 << n)
        need = [0] * (1 << n)

        return f[(1 << n) - 1]


class Solution:

    def minNumberOfSemesters(self, n: int, relations: List[List[int]],
                             k: int) -> int:
        pre = [0] * n
        for x, y in relations:
            pre[y - 1] |= 1 << (x - 1)
        q = deque()
        q.append((0, 0))
        tot = (1 << n) - 1
        v = [False] * (1 << n)
        while q:
            complete, time = q.popleft()
            if complete == tot:
                return time
            unfinish = tot ^ complete
            enum = unfinish
            while enum > 0:
                if enum.bit_count() <= k:
                    ok = True
                    for i in range(n):
                        if (enum >> i) & 1 == 1:
                            if pre[i] & complete != pre[i]:
                                ok = False
                                break
                    if ok and not v[complete | enum]:
                        q.append((complete | enum, time + 1))
                enum = (enum - 1) & unfinish


from heapq import heappop, heappush


class Solution:

    def minNumberOfSemesters(self, n: int, relations: List[List[int]],
                             k: int) -> int:
        need = [0] * (1 << n)
        for x, y in relations:
            need[1 << (y - 1)] |= 1 << (x - 1)
        for i in range(1, 1 << n):
            need[i] = need[i & (i - 1)] | need[i & -i]
        q = deque([(0, 0)])
        tot = (1 << n) - 1
        v = [False] * (1 << n)
        while q:
            time, complete = q.popleft()
            if complete == tot:
                return time
            unfinish = tot ^ complete
            enum = unfinish
            while enum > 0:
                if enum.bit_count() <= k:
                    if (need[enum]
                            | complete) == complete and not v[complete | enum]:
                        v[complete | enum] = True
                        q.append((time + 1, complete | enum))
                enum = (enum - 1) & unfinish


class Solution:

    def minNumberOfSemesters(self, n: int, relations: List[List[int]],
                             k: int) -> int:
        need = [0] * (1 << n)
        for x, y in relations:
            need[1 << (y - 1)] |= 1 << (x - 1)
        for i in range(1, 1 << n):
            need[i] = need[i & (i - 1)] | need[i & -i]

        v = [-1] * (1 << n)
        v[0] = 0
        q = deque([0])
        tot = (1 << n) - 1

        while q:
            complete = q.popleft()
            if complete == tot:
                return v[complete]
            unfinish = tot ^ complete
            enum = unfinish
            while enum > 0:
                if enum.bit_count() <= k:
                    if (need[enum]
                            | complete) == complete and -1 == v[complete
                                                                | enum]:
                        v[complete | enum] = v[complete] + 1
                        q.append(complete | enum)
                enum = (enum - 1) & unfinish


so = Solution()
print(so.minNumberOfSemesters(n=4, relations=[[2, 1], [3, 1], [1, 4]], k=2))
# print(so.minNumberOfSemesters(4, [[2, 1], [2, 4]], 2))
